package leetcode_回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合
 * 算法：
 *   回溯
 *   剪枝，这里使用剪枝可以快很多
 *   当 n = 7， k = 4 时，到 5 就不需要遍历了，因为只有 5 6 7，凑不到 4 了，直接剪去即可
 *   n - (k - tem.size()) + 1
 */
public class _77 {

    public static void main(String[] args) {
        System.out.println(new _77().combine(4, 2));
    }

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> tem = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(1, n, k, tem, ans);
        return ans;
    }
    public void dfs(int i, int n, int k, List<Integer> tem, List<List<Integer>> ans) {
        if (tem.size() == k) {
            ans.add(new ArrayList<>(tem));
            return;
        }
        for (int j = i; j <= n - (k - tem.size()) + 1; j++) {
            tem.add(j);
            dfs(j + 1, n, k, tem, ans);
            tem.remove(tem.size() - 1);
        }
    }
}
